package org.example.algorithm.dp;

public class MaxProductSolution {

    public static void main(String[] args) {
        int[] nums = {2, -3, 2};
        MaxProductSolution solution = new MaxProductSolution();
        int res = solution.maxProduct(nums);
        System.out.println(res);
    }

    //正向循环保存最大值，逆向循环保存最大值，两者取max
    //注：遇到0重置为1
    public int maxProduct(int[] nums) {
        int productForward = 1;
        int productBack = 1;
        int maxForward = Integer.MIN_VALUE;
        int maxBack = Integer.MIN_VALUE;
        for (int i=0;i<nums.length;i++) {
            if (nums[i] != 0) {
                productForward *= nums[i];
                maxForward = Math.max(maxForward, productForward);
            } else {
                productForward = 1;
                maxForward = Math.max(maxForward, 0);
            }
        }
        for (int j=nums.length-1;j>=0;j--) {
            if (nums[j] == 0) {
                productBack = 1;
                maxBack = Math.max(maxBack, 0);
            } else {
                productBack *= nums[j];
                maxBack = Math.max(maxBack, productBack);
            }
        }
        return Math.max(maxForward, maxBack);
    }

    //dp优化内存占用
    public int maxProduct2(int[] nums) {
        int preMax = nums[0];
        int preMin = nums[0];
        int res = preMax;
        for (int i=1;i<nums.length;i++) {
            //nums[i] >= 0
            if (nums[i] >= 0) {
                preMax = Math.max(preMax * nums[i], nums[i]);
                preMin = Math.min(preMin * nums[i], nums[i]);
            } else {
                //nums[i] < 0
                int tempMax = preMax;
                preMax = Math.max(preMin * nums[i], nums[i]);
                preMin = Math.min(tempMax * nums[i], nums[i]);
            }
            res = Math.max(res, preMax);
        }
        return res;
    }

    // dpMax[i]代表以i结尾的最大值,dpMin[i]代表以i结尾的最小值
    public int maxProduct1(int[] nums) {
        int[] dpMax = new int[nums.length];
        int[] dpMin = new int[nums.length];
        dpMax[0] = dpMin[0] = nums[0];
        int res = dpMax[0];
        for (int i=1;i<nums.length;i++) {
            //nums[i] >= 0
            if (nums[i] >= 0) {
                dpMax[i] = Math.max(dpMax[i-1] * nums[i], nums[i]);
                dpMin[i] = Math.min(dpMin[i-1] * nums[i], nums[i]);
            } else {
                //nums[i] < 0
                dpMax[i] = Math.max(dpMin[i-1] * nums[i], nums[i]);
                dpMin[i] = Math.min(dpMax[i-1] * nums[i], nums[i]);
            }
            res = Math.max(res, dpMax[i]);
        }
        return res;
    }
}
